/***************************************************************************************
 * Copyright (c) 2014-2022 Zihao Yu, Nanjing University
 *
 * NEMU is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *          http://license.coscl.org.cn/MulanPSL2
 *
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 *
 * See the Mulan PSL v2 for more details.
 ***************************************************************************************/

#include <isa.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>
#include <string.h>
#include <memory/vaddr.h>

enum
{
  TK_NOTYPE = 256,
  TK_EQ,
  TK_INT,
  TK_NEQ,
  TK_LE,
  TK_GE,
  TK_AND,
  TK_OR,
  TK_HEX,
  TK_REG,
  DEREF

  /* TODO: Add more token types */

};

static struct rule
{
  const char *regex;
  int token_type;
} rules[] = {

    /* TODO: Add more rules.
     * Pay attention to the precedence level of different rules.
     */

    {" +", TK_NOTYPE},                        // spaces
    {"\\+", '+'},                             // plus
    {"-", '-'},                               // subtraction
    {"\\*", '*'},                             // multiplication
    {"/", '/'},                               // division
    {"\\(", '('},                             // left bracket
    {"\\)", ')'},                             // right bracket
    {"==", TK_EQ},                            // equal
    {"!=", TK_NEQ},                           // not equal
    {"<=", TK_LE},                            // less or equal
    {">=", TK_GE},                            // greater or equal
    {"&&", TK_AND},                           // logical and
    {"\\|\\|", TK_OR},                        // logical or
    {"^0x[0-9a-f]+|^0X[0-9A-F]+", TK_HEX},    // hexadecimal number
    {"^[1-9][0-9]*|^0", TK_INT},                  // integer
    {"^\\$[0-9a-z]+", TK_REG}, // register name

};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex()
{
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i++)
  {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0)
    {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token
{
  int type;
  char str[32];
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used)) = 0;

// static int op[32], fop=-1;
// static int digit[32], fdig=-1;
static bool make_token(char *e)
{
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0')
  {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i++)
    {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0)
      {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */

        switch (rules[i].token_type)
        {
        case TK_NOTYPE:
          break;
        default:
        {
          tokens[nr_token].type = rules[i].token_type;
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          nr_token++;
        }
        }

        break;
      }
    }

    if (i == NR_REGEX)
    {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

bool check_parentheses(int p, int q)
{
  if (tokens[p].type != '(' || tokens[q].type != ')')
  {
    return false;
  }
  int cnt = 0;
  for (int i = p; i <= q; i++)
  {
    if (tokens[i].type == '(')
      cnt++;
    else if (tokens[i].type == ')')
      cnt--;
    if (i != q && cnt <= 0)
      return false;
  }
  return cnt == 0;
}

int operator_level(int op_type)
{
  switch (op_type)
  {
  case '+':
    return 1;
  case '-':
    return 1;
  case '*':
    return 2;
  case '/':
    return 2;
  case TK_AND:
    return -1;
  case TK_OR:
    return -1;
  case TK_GE:
    return 0;
  case TK_LE:
    return 0;
  case TK_EQ:
    return 0;
  case TK_NEQ:
    return 0;
  default:
    return 3;
  }
  return -1;
}

bool is_certain_type(int type)
{
  return type == '+' ||
         type == '-' ||
         type == '*' ||
         type == '/' ||
         type == '(' ||
         type == TK_EQ ||
         type == TK_NEQ ||
         type == TK_LE ||
         type == TK_GE ||
         type == TK_AND ||
         type == TK_OR;
}

word_t eval(int p, int q)
{
  if (p > q)
  {
    if (tokens[p].type == DEREF)
      return 0;
    printf("undefined expression\n");
    assert(0);
    return 0;
  }
  else if (p == q)
  {
    assert(tokens[p].type == TK_INT || tokens[p].type == TK_HEX || tokens[p].type == TK_REG);
    switch (tokens[p].type)
    {
    case TK_INT:
    {
      word_t x;
      sscanf(tokens[p].str, "%lu", &x);
      return x;
    }
    case TK_HEX:
    {
      word_t x;
      sscanf(tokens[p].str, "%lx", &x);
      return x;
    }
    case TK_REG:
    {
      char* Reg_name = strtok(tokens->str, "$");
      if(strcmp(Reg_name, "0") == 0){
        strcpy(Reg_name, "$0");
      }
      bool success;
      word_t x = isa_reg_str2val(Reg_name, &success);
      if(success){
        return x;
      }
      else{
        Log("wrong register name");
        assert(0);
      }
    }
    default:
      break;
    }
  }
  else if (check_parentheses(p, q))
  {
    return eval(p + 1, q - 1);
  }
  else
  {
    int op = 0, op_type = 0, op_level = 3;
    bool is_in_parentheses = false;
    for (int i = p; i < q; i++)
    {
      if(tokens[i].type == '(') 
        is_in_parentheses = true;
      else if(tokens[i].type == ')')
        is_in_parentheses = false;
      if(is_in_parentheses)
        continue;
      if (is_certain_type(tokens[i].type) && operator_level(tokens[i].type) <= op_level)
      {
        op = i;
        op_type = tokens[i].type;
        op_level = operator_level(op);
      }
    }

    word_t val1 = eval(p, op - 1);
    word_t val2 = eval(op + 1, q);

    switch (op_type)
    {
    case '+':
      return val1 + val2;
    case '-':
      return val1 - val2;
    case '*':
      return val1 * val2;
    case '/':
      return val1 / val2;
    case TK_AND:
      return val1 && val2;
    case TK_OR:
      return val1 || val2;
    case TK_EQ:
      return val1 == val2;
    case TK_NEQ:
      return val1 != val2;
    case TK_GE:
      return val1 >= val2;
    case TK_LE:
      return val1 <= val2;
    case TK_REG:
    {
      bool success;
      word_t result = isa_reg_str2val(tokens[op].str + 1, &success);
      if (success)
        return result;
      else
      {
        printf("can't read the register file");
        assert(0);
      }
    }
    case DEREF:
      return vaddr_read(val2, sizeof(word_t));
    default:
      assert(0);
    }
  }
  return 0;
}

word_t expr(char *e, bool *success)
{
  init_regex();
  if (!make_token(e))
  {
    *success = false;
    return 0;
  }

  /* TODO: Insert codes to evaluate the expression. */

  for (int i = 0; i < nr_token; i++)
  {
    if (tokens[i].type == '*' && (i == 0 || is_certain_type(tokens[i - 1].type)))
    {
      tokens[i].type = DEREF;
    }
  }
  *success = true;
  word_t result = eval(0, nr_token - 1);
  return result;
}
